package com.douma.第13天;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;

/**
 * 抖码算法，让算法学习变的简单有趣
 *
 * @作者 : 老汤
 */
public class 最长广播响应 {
    /*
题目 2：最长广播响应

某通信网络中有 N 个网络结点，用 1 到 N 进行标识。
网络中的结点互联互通，且结点之间的消息传递有时延，相邻结点的时延均为 1 个时间单位
现给定网络结点的连接关系 link[i] = {u, v}，其中 u 和 v 表示网络结点
当指定一个结点向其他结点进行广播，所有被广播结点收到消息后，都会在原路径上回复一条响应消息
请计算发送结点至少需要等待几个单位时间才能收到所有被广播结点的响应消息。

注：
① N 的取值范围为 [0,100]
② 连接关系 link 的长度不超过 3000，且 1 <= u, v <= N
③ 网络中任意结点均可达

输入描述：
输入第一行为两个正整数，分别表示网络结点的个数 N，以及时延列表的长度 I
接下来的 I 行输入，表示结点的连接关系列表
最后一行的输入为一个正整数，表示指定的广播结点序号

输出描述：
输出一个整数，表示发送点接收到所有响应消息至少需要等待的时长

示例 1：
输入
5 7
2 1
1 4
2 4
2 3
3 4
3 5
4 5
2

输出：
4

说明：2 到 5 的最小时延是 2 个单位时间
而 2 到其他结点的最小时延是 1 个时间单位
所以 2 收到所有节点的最大响应时间为 2 * 2 = 4
     */

    private static TreeSet<Integer>[] graph;
    private static boolean[] visited;

    // 记录最大距离
    private static int maxDis = 0;

    // 思路：这道题目的本质就是求图的单源最长路径，使用 BFS 可以实现
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int l = sc.nextInt();
        sc.nextLine();

        // 1. 构建图
        graph = new TreeSet[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new TreeSet<>();
        }

        for (int i = 0; i < l; i++) {
            // 减 1 是因为：顶点是从 1 开始，而数组下标是从 0 开始的
            int v = sc.nextInt() - 1;
            int w = sc.nextInt() - 1;
            graph[v].add(w);
            graph[w].add(v);

            sc.nextLine();
        }

        visited = new boolean[n];

        // 2. 从源点开始 BFS (一层一层遍历)，求最大的层数
        int source = sc.nextInt() - 1;
        bfs(source);

        // maxDis 包含了 source 这个点，所以需要减去
        System.out.println((maxDis - 1) * 2);

        sc.close();
    }

    private static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;

        while (!queue.isEmpty()) {
            // 遍历一层
            maxDis++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();

                for (int w : graph[curr]) {
                    if (!visited[w]) {
                        queue.add(w);
                        visited[w] = true;
                    }
                }
            }
        }
    }
}
